package com.mxw.leetcode.D2动态规划;

public class D14零钱兑换2 {

    /**

     给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
     请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回0。
     假设每一种面额的硬币有无限个。
     题目数据保证结果符合 32 位带符号整数。

     输入：amount = 5, coins = [1, 2, 5]
     输出：4
     解释：有四种方式可以凑成总金额：
     5=5
     5=2+2+1
     5=2+1+1+1
     5=1+1+1+1+1

     输入：amount = 3, coins = [2]
     输出：0
     解释：只用面额 2 的硬币不能凑成总金额 3 。

     输入：amount = 10, coins = [10]
     输出：1

     转为背包问题：
     有一个背包，最大容量为 amount，有一系列物品 coins，每个物品的重量为 coins[i]，每个物品的数量无限。请问有多少种方法，能够把背包恰好装满？
     这个问题和我们前面讲过的两个背包问题，有一个最大的区别就是，每个物品的数量是无限的，这也就是传说中的「完全背包问题」，没啥高大上的，
     无非就是状态转移方程有一点变化而已。

     dp[i][j] 的定义如下：
     若只使用前 i 个物品（可以重复使用），当背包容量为 j 时，有 dp[i][j] 种方法可以装满背包。
     换句话说，翻译回我们题目的意思就是：
     若只使用 coins 中的前 i 个（i 从 1 开始计数）硬币的面值，若想凑出金额 j，有 dp[i][j] 种凑法。
     经过以上的定义，可以得到：

     如果你不把这第 i 个物品装入背包，也就是说你不使用 coins[i-1] 这个面值的硬币，那么凑出面额 j 的方法数 dp[i][j] 应该等于 dp[i-1][j]，继承之前的结果。
     如果你把这第 i 个物品装入了背包，也就是说你使用 coins[i-1] 这个面值的硬币，那么 dp[i][j] 应该等于 dp[i][j-coins[i-1]]。
     我们想求的 dp[i][j] 是「共有多少种凑法」，所以 dp[i][j] 的值应该是以上两种选择的结果之和：
     dp[i][j] = dp[i - 1][j]+ dp[i][j-coins[i-1]];


     */
    int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp =new int[n + 1][amount + 1];
        // base case
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= amount; j++) {
                if (j - coins[i-1] >= 0) {
                    //使用 coins[i-1] 这个面值的硬币，那么 dp[i][j] 应该等于 dp[i][j-coins[i-1]]。
                    //决定使用这个面值的硬币，那么就应该关注如何凑出金额 j - coins[i-1]。
                    //比如说，你想用面值为 2 的硬币凑出金额 5，那么如果你知道了凑出金额 3 的方法，再加上一枚面额为 2 的硬币，不就可以凑出 5 了嘛。
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i-1]];
                } else {
                    //不使用 coins[i-1] 这个面值的硬币
                    //那么凑出面额 j 的方法数 dp[i][j] 应该等于 dp[i-1][j]，继承之前的结果。
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n][amount];
    }
}
